package com.fengdi.book.hard.design;

class Trie {
    private final TrieNode root;
    // 前缀树节点
    class TrieNode {
        public char value = ' ';
        public TrieNode[] childs = new TrieNode[26];
        boolean isEnd = false;
        public TrieNode(){}

        public TrieNode(char value) {
            this.value = value;
        }
    }

    public Trie() {
        this.root = new TrieNode();
    }

    public void insert(String word) {
        if(word.isEmpty()) return;
        char[] chs = word.toCharArray();
        TrieNode p = this.root;
        for(char c : chs) {
            int cASCII = c - 'a';
            if(p.childs[cASCII] == null) {// 创建新节点
                TrieNode node = new TrieNode(c);
                p.childs[cASCII] = node;
            }
            p = p.childs[cASCII];
        }
        p.isEnd = true;
    }

    public boolean search(String word) {
        if(word.isEmpty()) return true;

        char[] chs = word.toCharArray();
        TrieNode p = this.root;
        for(char c : chs) {
            int cASCII = c - 'a';
            if(p.childs[cASCII] == null) return false;
            p = p.childs[cASCII];
        }
        return p.isEnd;
    }

    public boolean startsWith(String prefix) {
        if(prefix.isEmpty()) return true;
        char[] chs = prefix.toCharArray();
        TrieNode p = this.root;

        for(char c : chs) {
            int cASCII = c - 'a';
            if(p.childs[cASCII] == null) return false;
            p = p.childs[cASCII];
        }
        return true;
    }
}
